package leetcode.jianzhioffer;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-18 19:51
 **/
public class JianZhiOffer17 {

    /*public int[] printNumbers(int n) {
        int max = (int)Math.pow(10, n);
        int[] res = new int[max - 1];
        for (int i = 1; i < max; i++) {
            res[i - 1] = i;
        }
        return res;
    }*/

   /* StringBuilder res;
    int count = 0, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public String printNumbers(int n) {
        this.n = n;
        res = new StringBuilder(); // 数字字符串集
        num = new char[n]; // 定义长度为 n 的字符列表
        dfs(0); // 开启全排列递归
        res.deleteCharAt(res.length() - 1); // 删除最后多余的逗号
        return res.toString(); // 转化为字符串并返回
    }
    void dfs(int x) {
        if(x == n) { // 终止条件：已固定完所有位
            res.append(String.valueOf(num) + ","); // 拼接 num 并添加至 res 尾部，使用逗号隔开
            return;
        }
        for(char i : loop) { // 遍历 ‘0‘ - ’9‘
            num[x] = i; // 固定第 x 位为 i
            dfs(x + 1); // 开启固定第 x + 1 位
        }
    }*/

    //左边界，分隔第一个非0字符
    int start;
    int  n;
    //当进位之后，start就要左移一位
    int nine;
    char[] loop = {'0','1','2','3','4','5','6','7','8','9'};
    char[] nums;
    StringBuilder builder;
    public String printNumbers(int n) {
       this.n = n;
       start = n -1;
       nums = new char[n];
       builder = new StringBuilder();
       dfs(0);
       builder.deleteCharAt(builder.length() - 1);
       return builder.toString();
    }
    void dfs(int x) {
        if (x == n) {
            //截取自左边界非0的字符串
            String s = String.valueOf(nums).substring(start);
            if (!"0".equals(s)) {
                builder.append(s).append(",");
            }
            if (n - start == nine) {
                start--;
            }
            return;
        }
        for (char c : loop) {
            if (c == '9') {
                nine++;
            }
            nums[x] = c;
            dfs(x + 1);
        }
        nine--;
    }





    public static void main(String[] args) {
        JianZhiOffer17 offer = new JianZhiOffer17();
        System.out.println(offer.printNumbers(2));
    }


}
